package _array

import org.junit.Assert
import org.junit.Test

/**
 * https://programmercarl.com/0977.%E6%9C%89%E5%BA%8F%E6%95%B0%E7%BB%84%E7%9A%84%E5%B9%B3%E6%96%B9.html
 * https://leetcode.cn/problems/squares-of-a-sorted-array/description/
 * 给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
 *
 * 输入：nums = [-4,-1,0,3,10]
 * 输出：[0,1,9,16,100]
 *
 * 输入：nums = [-7,-3,2,3,11]
 * 输出：[4,9,9,49,121]
 */
class Test7 {
    @Test
    fun test_1() {
        val nums = intArrayOf(-4, -1, 0, 3, 10)
        val actual = Solution().sortedSquares(nums)
        val expect = intArrayOf(0, 1, 9, 16, 100)
        Assert.assertEquals(expect.contentToString(), actual.contentToString())
    }

    @Test
    fun test_2() {
        val nums = intArrayOf(-7, -3, 2, 3, 11)
        val actual = Solution().sortedSquares(nums)
        val expect = intArrayOf(4, 9, 9, 49, 121)
        Assert.assertEquals(expect.contentToString(), actual.contentToString())
    }

    private class Solution {
        // fun sortedSquares(nums: IntArray): IntArray {
        /**
        冒泡排序
        T - N + N * N
        S - 1

        先平方，再排序
        loop(i from 0 to N）{
        loop(j from i to N)){
        if(i < j) swipe
        }
        }
         */
        //  val end = nums.size-1
        //  for(i in 0 .. end){
        //     nums[i] = nums[i] * nums[i]
        //  }
        //  println(nums.contentToString())

        //  var t:Int
        //  for(i in 0 .. end){
        //     for(j in i .. end){
        //         if(nums[i] > nums[j]){
        //             t = nums[j]
        //             nums[j] = nums[i]
        //             nums[i] = t
        //         }
        //     }
        //  }

        //  return nums
        // }

        // fun sortedSquares(nums: IntArray): IntArray {
        //     /**
        //     T - O(nlogn)
        //     S - O(logn)

        //     先平方，再排序
        //      */
        //      val end = nums.size-1
        //      for(i in 0 .. end){
        //         nums[i] = nums[i] * nums[i]
        //      }
        //      println(nums.contentToString())

        //     nums.sort()

        //      return nums
        // }


        fun sortedSquares(nums: IntArray): IntArray {
            /**
            T - O(N)
            S - O(1)

            双指针法
             */
            val end: Int = nums.size - 1
            val r: IntArray = IntArray(end + 1)

            var i: Int = 0;
            var j: Int = end;
            var pos: Int = end
            var left: Int
            var right: Int
            while (i <= j) {
                left = nums[i] * nums[i]
                right = nums[j] * nums[j]
                if (left < right) {
                    r[pos] = right
                    j--
                } else {
                    r[pos] = left
                    i++
                }
                pos--
            }

            return r
        }
    }
}